package minOperations;

import java.util.*;

public class Solution {
    public int minOperations(List<Integer> nums, int target) {
//        long s = 0;
//        var cnt = new long[31];
//        for (int x : nums) {
//            s += x;
//            cnt[Integer.numberOfTrailingZeros(x)]++;
//        }
//        if (s < target)
//            return -1;
//        int ans = 0, i = 0;
//        s = 0;
//        while ((1L << i) <= target) {
//            s += cnt[i] << i;
//            int mask = (int) ((1L << ++i) - 1);
//            if (s >= (target & mask))
//                continue;
//            ans++; // 一定要找更大的数操作
//            for (; cnt[i] == 0; i++)
//                ans++; // 还没找到，继续找更大的数
//        }
//        return ans;


        long s = 0;
        long[] cnt = new long[31];
        for (int x: nums) {
            s+=x;
            cnt[Integer.numberOfTrailingZeros(x)]++;
        }
        if(s<target) return -1;
        int ans = 0,i = 0;
        s = 0;
        while ((1L<<i)<=target) {
            s+=cnt[i]<<i;
            int mask = (int)((1L<<++i)-1);
            if(s>=(target&mask))
                continue;
            ans++;
            for (; cnt[i]==0; i++) {
                ans++;
            }
        }
        return ans;
    }
}
